package dynamicProgramming.baseKnowledge;

/**
 * @author zxc
 * @date 2023/01/18 10:30
 **/
/**
 * 题目 ：爬楼梯的最少成本
 * 题目详述 ：
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 提示：
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 */
public class MinCostClimbingStairs_redisRecursion {
    public static void main(String[] args) {
        int[] cost = new int[]{1 , 100};
        minCostClimbingStairs(cost);
    }
    /**
     * 思路 ：
     * 为解决使用递归直接实现状态转移方程的大量重复计算，可以使用缓存redis将已经求解过的f(i)记录下来;
     * （使用缓存记录的话，后续遇到重复记录的话，直接使用缓存中数据即可，不需要取再次进行计算）
     * 核心，在于求解f(i - 1) 和 f(i - 2)这两个子问题会出现重叠计算;
     * @param cost
     * @return
     */
    public static int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        // 初始化一个缓存数组redis，用来存储 从每级台阶继续向上爬所需要的最少成本;
        int[] redis = new int[length];
        if(length == 2){
            return Math.min(cost[0] , cost[1]);
        }
        else {
            /**
             * 此处的递归算法存在问题 ：
             * 限制条件 ：2 <= cost.length <= 1000（即，cost数组至少有两个及以上的元素）
             * （1）若是所传入的有且恰好只有两个元素的话，只会进入redisRecursion递归方法的第一个if语句，将redis[1] = cost[1];
             * （2）后面的else if语句进行判断时，由于在上面的if语句中已经给redis[1]赋值，所以不会进入else if;
             * （3）===》导致了redis[0]为空，未能使得redis[0] = cost[0];
             */
            redisRecursion(cost , length - 1 , redis);
            return Math.min(redis[length - 1] , redis[length - 2]);
        }
        // 由于redis缓存数组中所存储的是从每级台阶继续向上爬所需要的最少成本，同时又由于每次能够向上爬一级或者两级台阶
        // ===》 所以只需要去求取Math.min(从第length - 1台阶向上爬的最少成本（即，只需要再向上爬一层台阶就能够登顶）,
        //                             从第length - 2台阶向上爬的最少成本（即，只需要再向上爬两层台阶就能够登顶）)
    }
    // redisRecusion方法 ：即代表了向redis缓存数组中存储 从第index级台阶继续向上爬所需要花费的最少成本;
    // 递归实现 ：即，从大问题入手，将f(i)分解成两个子问题f(i - 1)和f(i - 2);
    // ===> 即，这种从大问题入手，逐渐将大问题分解成一个个子问题的过程，是一种自上而下的求解过程;
    private static void redisRecursion(int[] cost, int length, int[] redis) {
        if(length < 2){
            redis[length] = cost[length];
        }
        // 有且仅当redis[length]还未存储过 从length级台阶继续向上爬所需要的最少成本
        else if(redis[length] == 0){
            // 通过递归去获取 从第length - 1/length - 2级台阶开始向上爬所需要花费的最小成本;
            // 同时将所获取的结果，存储到 redis[length - 1]/redis[length - 2]，
            // 即保证了后续去获取 从第length - 1/length - 2级台阶开始向上爬所需要花费的最小成本，
            // 只需要去缓存数组redis中获取 redis[length - 1]/redis[length - 2]即可;
            redisRecursion(cost , length - 1 , redis);
            redisRecursion(cost , length - 2 , redis);
            // 为求取redis[length]（从第length级台阶开始向上爬所需要花费的最小成本）,
            // ===》 需要获取到redis[length - 1]（从第length - 1级台阶开始向上爬所需要花费的最小成本）
            //       + redis[length - 2]（从第length - 2级台阶开始向上爬所需要花费的最小成本）
            redis[length] = Math.min(redis[length - 1] , redis[length - 2]) + cost[length];
        }
    }
}
